
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <pthread.h>
#include "controleEleicao.h"
#define MAX_LINHA 999

/**
 * Estrutura para passar os parâmetros necessários a uma thread para o cálculo das instâncias
 */
typedef struct {
	int id;			//ID da thread
	int inicio;
	int fim;
	int n;
	int **matriz;
	int **permutacao;
} ThreadScore;


/**
 * Faz a alocação dinâmica de uma matriz de inteiros
 *
 * m -> número de linhas da matriz
 * n -> número de colunas da matriz
 */

int ** alocaMatriz(int m, int n) {
	int **v;
	int   i;
	if (m < 1 || n < 1) {
		printf ("** Erro: Parametro invalido **\n");
		return (NULL);
	}

	v = (int **) calloc (m, sizeof(int *));
	if (v == NULL) {
		printf ("** Erro: Memoria Insuficiente **");
		return (NULL);
	}

	for ( i = 0; i < m; i++ ) {
		v[i] = (int*) calloc (n, sizeof(int));
		if (v[i] == NULL) {
			printf ("** Erro: Memoria Insuficiente **");
			return (NULL);
		}
	}
	return (v);
}


/**
 * Cria uma matriz que representa o numero de votos na preferencia para a par entre os canidatos
 *
 * lv -> lista encadeada do tipo ListaVoto
 */
int **criarMatriz(ListaVoto lv) {

	ListaCandidato lc = lv.Primeiro->prox->itemVoto.candidatos;

	int totalCandidatos = obterNumeroCandidatos(lc);
	int **matriz = alocaMatriz(totalCandidatos,totalCandidatos);
	int i,j;

	//inicializa matriz com zeros
	for(i = 0; i < totalCandidatos; i++) {
		for(j = 0; j < totalCandidatos; j++) {
			matriz[i][j] = 0;
		}
	}

	for(i = 0; i < totalCandidatos; i++) {
		for(j = 0; j < totalCandidatos; j++) {

			int somatorio = 0;

			if( i == j) {
				continue;
			}

			PVoto aux = lv.Primeiro->prox;
			while (aux != NULL)
			{
				int qtdVotos = aux->itemVoto.votos;

				PCandidato auxCandidato = aux->itemVoto.candidatos.Primeiro->prox;

				while (auxCandidato != NULL) {

					if(auxCandidato->itemCandidato.candidato == (i+1)) {
						somatorio += qtdVotos;
						break;
					} else if(auxCandidato->itemCandidato.candidato == (j+1)) {
						break;
					} else{
						//faz nada
					}
					auxCandidato = auxCandidato->prox;
				}

				aux = aux->prox;
			}

			matriz[i][j] = somatorio;
		}
	}

	return matriz;

}

int obterTotalPermutacoes(int valor) {

	if(valor == 1) {
		return 1;
	}

	return valor * obterTotalPermutacoes(valor-1);
}

/**
 * Método para a partir de uma lista encadeada de ListaVoto
 * preparar um vetor com o tamanho igual ao número de candidatos
 * e gerar todas as suas permutações (possibilidades de votos)
 *
 * lv -> lista encadeada do tipo ListaVoto
 */
int **gerarPermutacao(ListaVoto lv) {

	ListaCandidato lc = lv.Primeiro->prox->itemVoto.candidatos;

	int numCandidatos = obterNumeroCandidatos(lc);
	int numPermutacoes = obterTotalPermutacoes(numCandidatos);
	int candidatos[numCandidatos];
	int **permutacao = alocaMatriz(numPermutacoes, numCandidatos);
	int indice = 0;

	int i;
	for(i = 0; i < numCandidatos; i++) {
		candidatos[i] = i+1;
	}

	permute(permutacao, candidatos,0,numCandidatos, &indice);

	return permutacao;
}

/**
 * Método para fazer a permutação dos elementos de um vetor
 *
 * permutacao -> matriz que ao final da execução irá conter os elementos permutados
 * v -> vetor que será permutado
 * start -> controle do índice do vetor, deve ser inicializado com 0
 * n -> tamanho do vetor
 * indice -> ponteiro para percorrer as linhas da matriz de permutaçao, deve ser inicializado com 0
 *
 */
void permute(int **permutacao, int *v, int start, int n, int *indice) {

	if (start == n-1) {
		int i;
		for(i = 0; i < n; i++) {
			permutacao[*indice][i] = v[i];
		}
		*indice = *indice+1;
	} else {
		int i;
		for (i = start; i < n; i++) {
		  int tmp = v[i];

		  v[i] = v[start];
		  v[start] = tmp;
		  permute(permutacao, v, start+1, n, indice);
		  v[start] = v[i];
		  v[i] = tmp;
		}
	}
}

/**
 * Método usado para paralelizar o cálculo do score das instâncias, o intervalo analisado
 *
 * O método retorna um vetor de inteiros com duas posições em que:
 *   - a posição 0 possui o índice do vetor que obteve o maior score do intervalo analisado
 *   - a posicção 1 possui o maior score obtido do intervalo analisado
 */
void *thread_score(void *arg) {

	int *vetor = NULL;
	int i,j,k;

	int maiorValor = 0;
	int maiorIndice = 0;

	ThreadScore *t = (ThreadScore*) arg;
	int inicio = t->inicio;
	int fim = t->fim;
	int n = t->n;
	int **matriz = t->matriz;
	int **permutacao = t->permutacao;

	if(fim <= inicio) {
		return (NULL);
	}


	for(k = inicio; k < fim; k++) {
		int score = 0;
		for(i = 0; i < n; i++) {
			for(j = i; j < n; j++) {
				int linha = permutacao[k][i];
				int coluna = permutacao[k][j];
				score += matriz[linha-1][coluna-1];
			}
		}

		if(score > maiorValor) {
			maiorIndice = k;
			maiorValor = score;
		}
	}

	vetor = (int*)malloc(sizeof(char)*2);
	vetor[0] = maiorIndice;
	vetor[1] = maiorValor;

	return vetor;
}

/**
 * Calcula o resultado da eleição com base nas permutações e na matriz de preferências
 *
 * permutacao -> matriz com todas as possibilidades de votos
 * matriz -> matriz de preferência entre os candidatos
 * n -> numero de colunas nas duas matrizes
 */
char *calcularResultado(int **permutacao, int **matriz, int n, int numThreads) {
	int cont,k;
	int permutacoes = obterTotalPermutacoes(n);

	int maiorValor = 0;
	int maiorIndice = 0;

	ThreadScore param[numThreads];
	pthread_t thread_ID[numThreads];

	int grupo = permutacoes / numThreads;
	int indiceGrupo = 0;
	void *exit_status = NULL;

	for(cont = 0; cont < numThreads; cont++) {
		ThreadScore value;
		value.inicio = indiceGrupo;
		value.n = n;
		value.matriz = matriz;
		value.permutacao = permutacao;

		if ( cont == (numThreads - 1))
			value.fim = permutacoes;
		else
			value.fim = grupo + indiceGrupo;

		param[cont] = value;
	}

	//inicia as threads para o cálculo do score em uma região das permutações geradas
	for(cont = 0; cont < numThreads; cont++ ) {
		pthread_create(&thread_ID[cont] , NULL, thread_score , &param[cont] ) ;
	}

	//termina as threads e obtém o maior score e o seu índice entre as diversas threads
	for(cont = 0; cont < numThreads; cont++ ) {
		pthread_join( thread_ID[cont] , &exit_status ) ;
		if(exit_status != NULL) {
			int *maiores = (int*) exit_status;
			if(maiores[1] > maiorValor) {
				maiorValor = maiores[1];
				maiorIndice = maiores[0];
			}
		}
	}

	char *retorno = (char*)malloc(sizeof(char)*MAX_LINHA);

	for(k=0; k < n; k++) {

		char numero[4];
		sprintf(numero, "%s%d ", "", permutacao[maiorIndice][k]);
		strcat(retorno,numero);
	}

	sprintf(retorno, "%s%d ", retorno, maiorValor);


	return retorno;


}


/*Metodos para manipular a lista de candidatos*/

int isListaCandidatoVazia(ListaCandidato L) {
	return (L.Primeiro->prox == NULL);
}

void criarListaCandidato(ListaCandidato *L) {
	L->Primeiro = (PCandidato)malloc(sizeof(Candidato));
	L->Ultimo = (PCandidato)malloc(sizeof(Candidato));
	L->Primeiro->prox = NULL;
	L->Ultimo->prox = NULL;
}

int obterNumeroCandidatos(ListaCandidato L) {

	int contador = 0;

	PCandidato aux = L.Primeiro->prox;
	while (aux != NULL)
	{
		contador++;
		aux = aux->prox;
	}

	return contador;
}

void inserirPonteiroCandidato(ListaCandidato *L, PCandidato P) {
	if(isListaCandidatoVazia(*L))
		L->Primeiro->prox = P;
	else
	{
		L->Ultimo->prox->prox = P;
	}
	L->Ultimo->prox = P;
	P->prox = NULL;
}

void inserirCandidato(ListaCandidato *L,int candidato, int indice) {

	PCandidato P = (PCandidato)malloc(sizeof(Candidato));
	ItemCandidato item;
	item.candidato = candidato;
	item.indice = indice;


	P->itemCandidato = item;

	inserirPonteiroCandidato(L,P);
}

void imprimirCandidatos(ListaCandidato L) {

	PCandidato aux = L.Primeiro->prox;
	while (aux != NULL)
	{
		printf("\nCandidato %d, indice: %d", aux->itemCandidato.candidato, aux->itemCandidato.indice);
		aux = aux->prox;
	}
}

/*Metodos para manipular a lista de Votos*/
int isListaVotoVazia(ListaVoto L) {
	return (L.Primeiro->prox == NULL);
}

void criarListaVoto(ListaVoto *L) {
	L->Primeiro = (PVoto)malloc(sizeof(Voto));
	L->Ultimo = (PVoto)malloc(sizeof(Voto));
	L->Primeiro->prox = NULL;
	L->Ultimo->prox = NULL;
}

void inserirPonteiroVoto(ListaVoto *L, PVoto P) {

	if(isListaVotoVazia(*L))
		L->Primeiro->prox = P;
	else
	{
		L->Ultimo->prox->prox = P;
	}
	L->Ultimo->prox = P;
	P->prox = NULL;
}

void inserirVoto(ListaVoto *L, int votos, ListaCandidato LC) {

	PVoto P = (PVoto)malloc(sizeof(Voto));
	ItemVoto item;
	item.candidatos = LC;
	item.votos = votos;

	P->itemVoto = item;

	inserirPonteiroVoto(L,P);
}

void imprimirVotos(ListaVoto L) {

	PVoto aux = L.Primeiro->prox;
	while (aux != NULL)
	{
		printf("\nQtd votos %d ",aux->itemVoto.votos);
		imprimirCandidatos(aux->itemVoto.candidatos);
		aux = aux->prox;
	}
}

ListaCandidato *liberaCandidato(ListaCandidato L) {

	PCandidato p = L.Primeiro->prox;
	while (p != NULL) {
		PCandidato t = p->prox;
		free(p);
		p = t;
	}

	return (NULL);
}

ListaVoto *liberaVoto(ListaVoto L)
{
   PVoto p = L.Primeiro->prox;
   while (p != NULL) {
      PVoto t = p->prox;
      liberaCandidato(p->itemVoto.candidatos);
      free(p);
      p = t;
   }
   return (NULL);
}

int **liberaMatriz(int **matriz, int n) {

	int i;
	for(i = 0; i < n-1; i ++) {
		free(matriz[i]);
	}
	free(matriz);
	return (NULL);

}
